package tree;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

/**
 * @author songZiHao
 * @version 1.0.0
 * @ClassName BaseTree.java
 * @Description TODO
 * @createTime 2020年08月10日 20:37:00
 */
public class BinarySearchTree<E extends TreeComparable> implements Tree<E> {

	protected int size = 0;

	protected Node<E> root;

	protected TreeComparable<E> comparable;

	public BinarySearchTree(TreeComparable<E> comparable) {
		this.comparable = comparable;
	}

	protected static class Node<E extends TreeComparable> {
		E element;
		Node<E> left;
		Node<E> right;
		Node<E> parent;

		public Node(E element, Node<E> parent) {
			this.parent = parent;
			this.element = element;
		}

		public boolean isLeaf() {
			return left == null && right == null;
		}

		public boolean hasTwoChild() {
			return left != null && right != null;
		}

		public boolean hasLeftChild() {
			return left != null || right != null;
		}

		public boolean isLeftChild() {
			return parent != null && this == parent.left;
		}

		public boolean isRightChild() {
			return parent != null && this == parent.right;
		}

		public Node<E> sibling() {
			if (isLeftChild()) {
				return parent.right;
			}
			if (isRightChild()) {
				return parent.left;
			}
			return null;
		}
	}

	@Override
	public int size() {
		return size;
	}

	@Override
	public boolean isEmpty() {
		return size == 0;
	}

	@Override
	public void clear() {

	}

	@Override
	public void add(E element) {
		nullCheck(element);
		//添加第一个节点
		if (root == null) {
			root = new Node<>(element, null);
			size++;
			return;
		}
		Node<E> parent = root;
		Node<E> node = root;
		int cmp = 0;
		//节点不为空则继续进行比较，为空表示比较到了最后了
		while (node != null) {
			cmp = compare(element, node.element);
			//父节点为比较之后的大的或者小的节点
			parent = node;
			//新的节点比父节点大，就用父节点的右子节点进行比较
			if (cmp > 0) {
				node = node.right;
			} else if (cmp < 0) {//新的节点比父节点小，就用父节点的左子节点进行比较
				node = node.left;
			} else {//相等
				return;
			}
		}
		// 看看插入到父亲节点的哪个位置
		Node<E> newNode = createNode(element, parent);
		if (cmp > 0) {
			parent.right = newNode;
		} else {
			parent.left = newNode;
		}
		balanceTree(newNode);
		size++;
	}

	protected Node<E> createNode(E element, Node<E> parent) {
		return new Node<>(element, parent);
	}

	protected void balanceTree(Node<E> node) {
	}

	@Override
	public boolean conatins(E element) {
		return false;
	}

	public int high() {
		return high(root);
	}

	private int high(Node<E> node) {
		if (node == null) {
			return 0;
		}
		return 1 + Math.max(high(node.left), high(node.right));
	}


	@Override
	public void preorderTree() {
		preorderTreeByRecursive(root);
		inorderTreeByRecursive(root);
		postorderTreeByRecursive(root);
		//使用队列的方式，来实现层序遍历
		levelOrderTree();
		//使用非递归的前序遍历
		preorderTreeByNonRecursive(root);
		inorderTreeByNonRecursive(root);
		postorderTreeByNonRecursive(root);
	}

	private void postorderTreeByNonRecursive(Node<E> visitor) {
		if (visitor == null || root == null) {
			return;
		}
		Node<E> prev = null;
		Stack<Node<E>> stack = new Stack<>();
		stack.push(root);
		while (!stack.isEmpty()) {
			Node<E> top = stack.peek();
			if (top.isLeaf() || (prev != null && prev.parent == top)) {
				prev = stack.pop();
				System.out.println(prev.element);
			} else {
				if (top.right != null) {
					stack.push(top.right);
				}
				if (top.left != null) {
					stack.push(top.left);
				}
			}
		}
	}

	private void inorderTreeByNonRecursive(Node<E> visitor) {
		if (visitor == null || root == null) {
			return;
		}
		Node<E> node = visitor;
		Stack<Node<E>> stack = new Stack<>();
		while (true) {
			if (node != null) {
				stack.push(node);
				node = node.left;
			} else if (stack.isEmpty()) {
				return;
			} else {
				node = stack.pop();
				//访问node节点
				System.out.println(node.element);
				if (node.right != null) {
					node = node.right;
				}
			}
		}
	}

	private void preorderTreeByNonRecursive(Node<E> visitor) {
		if (visitor == null || root == null) {
			return;
		}
		Node<E> node = visitor;
		Stack<Node<E>> stack = new Stack<>();
		while (true) {
			if (node != null) {
				//访问node节点
				System.out.println(node.element);
				//将右子节点入栈
				if (node.right != null) {
					stack.push(node.right);
				}
				//向左走
				node = node.left;
			} else if (stack.isEmpty()) {
				return;
			} else {//如果左边为空，则右节点出栈
				node = stack.pop();
			}
		}
	}

	private void levelOrderTree() {
		if (root == null) {
			return;
		}
		int height = 0, levelSize = 1;
		Queue<Node<E>> queue = new LinkedList<>();
		//1. 将根节点入队
		queue.offer(root);
		//循环执行操作，直到队列为空
		while (!queue.isEmpty()) {
			//将队头结点出队，进行访问
			Node<E> node = queue.poll();
			levelSize--;
			//将出队的节点的左子节点入队
			if (node.left != null) {
				queue.offer(node.left);
			}
			//将出队的节点的右子节点入队
			if (node.right != null) {
				queue.offer(node.right);
			}
			//一层的左右节点访问完了之后，队列里面包含了下一层的所有的节点的个数,levelSize为0的时候则表示一层处理完了
			if (levelSize == 0) {
				levelSize = queue.size();
				height++;
			}
		}
	}

	private void postorderTreeByRecursive(Node<E> node) {
		if (node == null) {
			return;
		}
		//后续遍历左子树
		postorderTreeByRecursive(node.left);
		//后序遍历右子树
		postorderTreeByRecursive(node.right);
		//根节点
		System.out.println(node.element);
	}

	private void inorderTreeByRecursive(Node<E> node) {
		if (node == null) {
			return;
		}
		//先中序遍历左子树
		inorderTreeByRecursive(node.left);
		//根节点
		System.out.println(node.element);
		//最后中序遍历由子树
		inorderTreeByRecursive(node.right);
	}

	private void preorderTreeByRecursive(Node<E> node) {
		//节点为null则表示，遍历到了最后的一个节点了
		if (node == null) {
			return;
		}
		System.out.println(node.element);
		//直接访问左子节点
		preorderTreeByRecursive(node.left);
		//访问右子节点
		preorderTreeByRecursive(node.right);
	}

	/**
	 * 前驱结点：中序遍历时的前一个节点
	 * <p>
	 * 1. node.left != null 在左子树中
	 * <p>
	 * predecessor=node.left.right.right.right...
	 * <p>
	 * 终止条件：right为null
	 * <p>
	 * 2. node.left == null && node.parent!=null 在左父节点中
	 * <p>
	 * predecessor=node.parent.parent.parent.parent...
	 * <p>
	 * 终止条件：node在parent的右子树中
	 * <p>
	 * 3. node.left == null && node.right == null
	 * <p>
	 * 没有前驱节点
	 */
	private Node<E> predecessor(Node<E> node) {
		if (node == null) {
			return null;
		}
		Node<E> left = node.left;
		//前驱结点在左子树中  predecessor=node.left.right.right.right...  终止条件：right为null
		if (left != null) {
			while (left != null) {
				left = left.right;
			}
			return left;
		}
		//从父节点，祖父节点中寻找前驱结点
		while (node.parent != null && node == node.parent.left) {
			node = node.parent;
		}
		//node.parent == null  父节点为null，说明没有前驱
		//node == node.parent.right
		return node.parent;
	}

	/**
	 * 后继节点：中序遍历时的后一个节点
	 * <p>
	 * <p>
	 * 1. node.right != null 在左子树中
	 * <p>
	 * predecessor=node.right.left.left.left...
	 * <p>
	 * 终止条件：left为null
	 * <p>
	 * 2. node.right == null && node.parent!=null 在左父节点中
	 * <p>
	 * predecessor=node.parent.parent.parent.parent...
	 * <p>
	 * 终止条件：node在parent的左子树中
	 * <p>
	 * 3. node.right == null && node.parent == null
	 * <p>
	 * 没有前驱节点
	 */
	private Node<E> successor(Node<E> node) {
		if (node == null) {
			return null;
		}
		Node<E> right = node.right;
		if (right != null) {
			while (right != null) {
				right = right.left;
			}
			return right;
		}
		while (node.parent != null && node == node.parent.right) {
			node = node.parent;
		}
		return node.parent;
	}

	public void remove(E element) {
		remove(node(element));
	}

	private void remove(Node<E> node) {
		if (node == null) {
			return;
		}
		size--;
		/**
		 * - 先用前驱或者后继节点值覆盖原节点的值
		 * - 然后删除相应的前驱或者后继节点
		 * - 如果一个节点的度为2，那么，他的前驱，后继节点的度只可能是1或者0
		 */
		if (node.left != null && node.right != null) {//度为2
			//找到后继节点
			Node<E> successor = successor(node);
			//把要删除的节点值改为后继节点的值
			node.element = successor.element;
			//删除后继节点
			node = successor;
		}
		/**
		 * 删除节点  度为1 或者 0
		 * 度为1的节点
		 * - child是node.left 或者 child 是node.right
		 * - 用child替代node的代替
		 */
		Node<E> replacement = node.left != null ? node.left : node.right;
		//度为1
		if (replacement != null) {
			//更改parent
			replacement.parent = node.parent;
			//更改parent的left，right的指向
			if (node.parent == null) {//node是度为1的节点并且是根节点
				root = replacement;
			} else if (node == node.parent.left) {
				node.parent.left = replacement;
			} else {
				node.parent.right = replacement;
			}
			//被删除的节点
			afterRemove(node, replacement);
		} else if (node.parent == null) {//node是根节点
			root = null;
			//被删除的节点
			afterRemove(node, null);
		} else {//node是叶子节点
			if (node == node.parent.right) {
				node.parent.right = null;
			} else {
				node.parent.left = null;
			}
			//被删除的节点
			afterRemove(node, null);
		}
	}

	protected void afterRemove(Node<E> node, Node<E> replacement) {
	}

	private Node<E> node(E element) {
		Node<E> node = root;
		while (node != null) {
			int cmp = compare(element, node.element);
			if (cmp == 0) {
				return node;
			} else if (cmp > 0) {
				node = node.right;
			} else {
				node = node.left;
			}
		}
		return null;
	}


	/**
	 * todo 比较新节点和旧节点
	 *
	 * @param element1 元素1
	 * @param element2 元素2
	 * @return 比较结果 大于0 表示  element1>element2 如果等于0 表示 element1=element2 如果小于0 表示 element1<element2
	 * @author songzihao
	 */
	public int compare(E element1, E element2) {
		return 1;
	}

	private void nullCheck(E element) {
		if (element == null) {
			throw new IllegalArgumentException("参数不能为空");
		}
	}
}
